import java.util.*;

public class Solution1631 {
    int[] R=new int[]{1,0,-1,0};
    int[] C=new int[]{0,1,0,-1};
    int m;
    int n;
    private class UnionUtil{
        HashMap<Integer,Integer> Util;
        int Count;
        UnionUtil(){
            Util=new HashMap<>();
            Count=0;
        }
        int getCount(){
            return Count;
        }
        int find(int element){
            if(Util.containsKey(element)==false){
                Util.put(element,element);
                Count++;
            }
            if(Util.get(element)!=element){
                Util.put(element,find(Util.get(element)));
            }
            return Util.get(element);
        }
        boolean union(int x,int y){
            int rootx=find(x);
            int rooty=find(y);
            if(rootx==rooty){
                return false;
            }
            Util.put(rootx,rooty);
            Count--;
            return true;
        }
    }

    private int getIndex(int M,int N){
        return (n*M)+N;
    }

    public boolean check(UnionUtil util){
        if(util.Util.containsKey(0)==false){
            return false;
        }
        if(util.Util.containsKey(getIndex(m-1,n-1))==false){
            return false;
        }
        return util.find(0)== util.find((getIndex(m-1,n-1)));
    }

    public int minimumEffortPath(int[][] heights) {
        m=heights.length;
        n=heights[0].length;
        List<int[]> edgeList=new ArrayList<>();
        UnionUtil util=new UnionUtil();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < 2; k++) {
                    int newM=i+R[k];
                    int newN=j+C[k];
                    if(0<=newM&&newM< heights.length&&0<=newN&&newN< heights[0].length){
                        int high=Math.abs(heights[newM][newN]-heights[i][j]);
                        edgeList.add(new int[]{i,j,newM,newN,high});
                    }
                }
            }
        }
        Collections.sort(edgeList, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[4]-o2[4];
            }
        });
        for (int[] tmpEdge: edgeList) {
            util.union(getIndex(tmpEdge[0],tmpEdge[1]),getIndex(tmpEdge[2],tmpEdge[3]));
            if(check(util)){
                return tmpEdge[4];
            }
        }
        return 0;
    }

    public static void main(String[] args) {
        Solution1631 s=new Solution1631();
        System.out.println(s.minimumEffortPath(new int[][]{{3}}));
    }
}
